package com.sicheng.lc.周赛.分类.思维.先后顺序or逆序;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/29 15:10
 */
public class 统计数组中好三元组数目 {
    //https://leetcode.cn/problems/count-good-triplets-in-an-array/
    int[] p = new int[(int) 1e5], tree = new int[(int) (1e5 + 1)];
    int n;

    void add(int x) {
        for (; x <= n; x += x & (-x)) {
            tree[x]++;
        }
    }

    int query(int x) {
        int res = 0;
        for (; x > 0; x -= x & (-x)) {
            res += tree[x];
        }
        return res;
    }

    public long goodTriplets(int[] nums1, int[] nums2) {
        init(nums2);
        long res = 0;
        for (int x : nums1) {
            add(p[x] + 1);
            int less = query(p[x]);
            int r = n - p[x] - 1 - (query(n) - query(p[x] + 1));
            res += (long) r * less;
        }
        return res;
    }

    private void init(int[] nums) {
        n = nums.length;
        for (int i = 0; i < nums.length; i++) {
            p[nums[i]] = i;
        }
    }

    public static void main(String[] args) {
        统计数组中好三元组数目 s = new 统计数组中好三元组数目();
        int[] nums1 = {4, 0, 1, 3, 2}, nums2 = {4, 1, 0, 2, 3};
        System.out.println(s.goodTriplets(nums1, nums2));
    }
}
